package Other;

public class leet_72 {
}

class Solution_72{
    public int minDistance(String word1, String word2) {
        int word1Length = word1.length();
        int word2Length = word2.length();
        // 解决空的情况
        if(word1Length * word2Length == 0){
            return word1Length + word2Length;
        }

        int[][] myDp = getDp(word1, word2);
        return myDp[word1Length][word2Length];
    }

    // 构造dp数组
    public int[][] getDp(String word1, String word2){
        int word1Length = word1.length();
        int word2Length = word2.length();
        // 不考虑其中一个string为空的情况
        // 构建初始数组 构建的字符串匹配图是从 '' 开始的
        int[][] myDp = new int[word1Length+1][word2Length+1];
        myDp[0][0] = 0;
        for(int i=1; i<word1Length+1; i++){
            myDp[i][0] = i;
        }
        for(int i=1; i<word2Length+1; i++){
            myDp[0][i] = i;
        }
        for(int i=1; i<word1Length+1; i++){
            for(int j=1; j<word2Length+1; j++){
                // word1插入一个词
                int inLineWord1 = myDp[i-1][j] + 1;
                // word2 插入一个词
                int inLineWord2 = myDp[i][j-1] + 1;
                // 修改word1一个词
                int modifyWord1 = myDp[i-1][j-1];
                // 如果当前字符想同就不需要修改逻辑
                if(word1.charAt(i-1) != word2.charAt(j-1)){
                    modifyWord1 += 1;
                }
                // 最终距离
                int minDistance = findMinNum(inLineWord1, inLineWord2, modifyWord1);
                myDp[i][j] = minDistance;
            }
        }
        return myDp;
    }


    public int findMinNum(int value1, int value2, int value3){
        int lastValue = 0;
        if(value1 > value2){
            lastValue = value2;
        }else {
            lastValue = value1;
        }

        if(lastValue > value3){
            lastValue = value3;
        }
        return lastValue;
    }

}
